package ch2.link.single;

/**
 * 例2.13：有一个整数单链表L，设计一个算法逆置L中的所有结点。
 * 例如L=(1，2，3，4，5)，逆置后L=(5，4，3，2，1)
 */
public class Exam2_13 {
    // 双指针的迭代法
    // 带头结点的单链表逆置
    public static void reverse1(LinkListClass<Integer> L) {   // 例2.13的算法
        LinkNode<Integer> p = L.head.next, q;   // p指向首结点
        L.head.next = null;
        while (p != null) {
            q = p.next;             // 暂存后继结点p.next
            p.next = L.head.next;   // 修改p的next指向L的头结点
            L.head.next = p;        // 头结点的next指向p
            p = q;                  // 遍历下一个结点
        }
    }
    // 无头结点的单链表逆置
    public static LinkNode<Integer> reverse2(LinkListClass<Integer> L) {   // 例2.13的算法
        LinkNode<Integer> cur = L.head, pre=null, tmp;   // cur指向首结点
        while (cur != null) {
            tmp = cur.next;     // 暂存cur的后继结点cur.next
            cur.next = pre;     // 修改cur的next指向
            pre = cur;          // 头结点的next暂存cur
            cur = tmp;          // cur访问下一个结点
        }
        return pre;
    }
    // 递归法
    public static LinkNode<Integer> reverse3(LinkNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        LinkNode<Integer> last = reverse3(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    public static LinkNode<Integer> reverse4(LinkNode<Integer> head) {
        return recur(head, null);
    }
    private static LinkNode<Integer> recur(LinkNode<Integer> cur,
                                           LinkNode<Integer> pre) {
        if (cur == null) {
            return pre;
        }
        LinkNode<Integer> last = recur(cur.next, cur);
        cur.next = pre;
        return last;
    }

    public static void main(String[] args) {
        Integer[] a = {1, 2, 3, 4, 5};
        LinkListClass<Integer> L = new LinkListClass<>();
        L.CreateListR(a);
        System.out.println("L: " + L);

        System.out.println("逆置");
        reverse1(L);
        System.out.println("reverse1: " + L);

        L.CreateListR(a);
        L.head = reverse2(L);
        System.out.println("reverse2: " + L);

        L.CreateListR(a);
        L.head.next = reverse3(L.head.next);
        System.out.println("reverse3: " + L);

        L.CreateListR(a);
        L.head.next = reverse4(L.head.next);
        System.out.println("reverse4: " + L);

    }
}

